(navigation image)
Home American Libraries | Canadian Libraries | Universal Library | Community Texts | Project Gutenberg | Children's Library | Biodiversity Heritage Library | Additional Collections
Search: Advanced Search
Anonymous User (login or join us)
Upload
See other formats

Full text of "Minimal three variable NOR and NAND logic circuits"




1 I B HAHY 

OF THE 
U N IVERSITY 
Of ILLINOIS 

510,84 

I^6r 

no. 156-163 

c o p 2 






r 



^ATHEMP • 

DIGITAL COMPUTER LABORATORY 
UNIVERSITY OF ILLINOIS 
URBANA, ILLINOIS 



REPORT NO, 162 



MINIMAL THREE-VARIABLE "NOR" AND "NAND" LOGIC CIRCUITS 



by 
Robert Allan Smith 



May 15, 196k 



(This work is being submitted in partial fulfillment of the requirements for 
the Degree of Master of Science. ) 



MTHEMA1 
LIBRARY 



Digitized by the Internet Archive 
in 2013 



http://archive.org/details/minimalthreevari162smit 






ACKNOWLEDGMENT 

The author wishes to express his sincere thanks to Professor 
To A, Murrell, his thesis advisor, for assistance in the preparation of this 
thesis. 



Return this book on or before the 
Latest Date stamped below. 

Theft, mutilation, and underlining of books 
are reasons for disciplinary action and may 
result in dismissal from the University. 
University of Illinois Library 



MAR B W87 



L161— O-1096 



TABLE OF CONTENTS 

Page 

1. INTRODUCTION 1 

2. DESCRIPTION OF THE PROGRAM 3 

2.1 The Universal Circuit 3 

2.2 Generation of Matrices k 

2.3 Processing of Matrices 5 

3. COMMENTS ON THE RESULTS .......... 6 

k. TABLE OF RESULTS ................. 7 

5. CIRCUIT DIAGRAMS . 18 

6. CONCLUSIONS ...... 20 

BIBLIOGRAPHY .... ................ 21 



-in 



MINIMAL THREE-VARIABLE "NOR" AND "NANIj" LOGIC CJ 
Robert Allan Smith, M.S. 
Department of Electrical Engineering 
University of Illinois, 196^ 

This paper presents a table of minimal NOR and NAND combinational 
circuits for the 256 logical functions of three variables, assuming complemented 
inputs are available. The circuits were found by an exhaustive method, using a 
computer. The criteria used for minimality were, first, minimality with respect 
to the number of logic elements, and second, minimality with respect to the 
total number of inputs to all elements, subject to the first condition. The 
results show that all 256 functions can be generated using five or fewer NOR or 
NAND elements. 



■IV- 



1. INTRODUCTION 

Circuits composed of NOR or NAND elements, while not the fastest type 
of circuits, are used extensively, mainly because of their economy--one type of 
element may be used throughout an entire circuit. Assuming the basic decision 
to use such "universal" elements has been made, the main design objective will 
usually be to produce either the fastest or the most economical circuit possible. 
The fastest NAND circuits, i.e., minimum levels, are obtained by rewriting the 
minimum-OR polynomial (as obtained by the Quine-McCluskey method) in terms of 
the NAND connective, yielding a three-level logic (two-level if complemented 
inputs are available). Similarly the minimum- AND polynomial may be written in 
terms of the NOR connective. Circuits obtained in this way are often also mini- 
mal with respect to the number of logic elements required. 

At present there are no known algebraic methods of obtaining absolutely 
minimal NOR or NAND circuits, or for that matter, circuits using any other types 

of logic elements. Methods such as the Quine-McCluskey method and the Karnaugh 

1 3 
map method ' give only near-to-minimal realizations. Recently, however, 

2 
Hellerman has reported the results of an exhaustive method utilizing a computer. 

The criteria used for minimality were, first, minimality with respect to the 

number of logic elements, and second, minimality with respect to the total number 

of inputs to all elements, subject to the first condition. Complemented inputs 

were assumed not available. 

In Hellerman ' s approach, a universal circuit configuration was set up 

which permitted systematic investigation of all the possible ways of connecting 

together a given number of NOR elements . The program began by generating as many 

functions as possible using one NOR element and storing the circuit configuration 

and the number of inputs required, in memory. Then, all possible configurations 

of two NOR elements were considered. If a particular function had been generated 



-1- 



previously with fewer elements or with the same number of elements but with 
fewer inputs, the configuration under consideration was discarded. If the func- 
tion had been generated previously with the same number of elements but with more 
inputs, the information regarding the configuration and the number of inputs 
replaced the previously stored information for that function. The program con- 
tinued in this way, up to seven NOR elements, and yielded a catalog of minimal 
NOR realizations for the 256 logical functions of three variables. Minimal NAND 
realizations were derived from the set of NOR realizations. 

The results reported in this thesis form an extension of Hellerman's 
work. A similar catalog is given, with the difference being that complemented 
inputs are assumed available. The same minimality criteria are used. The 
results show that with complemented inputs, all 256 functions can be generated 
using five or fewer NOR or NAND elements. 



2. DESCRIPTION OF THE PROGRAM 

The computer program was written in the assembler language SCATRE 
and was run on the IBM 709^+, the total running time being approximately 
35 minutes. The program considered NAND circuits rather than NOR circuits, and 
began with one NAND element, continuing up to four NAND elements, 

2.1 The Universal Circuit 

The universal circuit which allowed investigation of all possible 
configurations of four NAND elements is shown in Fig„ 1. 

Inputs 
a b c a b c 



123^56 7 89 



FIGURE 1. THE UNIVERSAL CIRCUIT 




Output 



Crossover points are either connected or disconnected, indicating which 
inputs feed the various elements. The circuit is then representable by a connec- 
tion matrix, a matrix of ones and zeros, each element of which indicates the 
presence or absence of a connection at the corresponding point in the circuit „ 

A separate computer word was used to represent each row of the matrix. Since 

30 ^ 9 
each connection point has two possible values, there are 2 ~ 10 possible 



-3- 



connection matrices. Many of these will, however, result in useless circui' 
and there are a number of restrictions which may be placed on the form of the 
connection matrix to eliminate these. Some restrictions are difficult to incor- 
porate into a program and some effect only a small saving of time. The following 
three restrictions were used in the final program: 

1. An input and its complement (e.g. , a and a) were not allowed 
to be fed into the same NAND element. 

2. Columns 1, 2, and 3 were "ordered," i.e., if A, B, and C 
represent the values of columns 1, 2, and 3 when considered 
as binary numbers, then it was required that 

A > B > C 

This means that the program investigated only one member 
from each of the 80 equivalence classes of functions of 
three variables, i.e., one member from each set of con- 
nection matrices whose members differ only in that they 
effect a permutation of input variables. 

3. Each element in the circuit had to be "useful," i.e., the 
output of every element (except the last) had to feed some 
other element. 

The number of matrices connecting four NAND elements which will pass 
the above restrictions is approximately 5 X 10 > a considerable saving over the 
original number. 

2.2 Generation of Matrices 

The systematic generation of matrices connecting four NANB elements 
was carried out as follows. Because of restriction 3j there are only 21 possible 
partial matrices consisting of columns 7, 8, and 9° These were stored in memory 



to be added to the remaining portion of the matrix. Because of restriction 1, 
there are only 27 permissible ways of "filling" the portion of any row up to 
column 6. These were similarly stored in 27 words. An outer program loop 
selected one of the 21 partial matrices for columns 7> 8, and 9- Inner loops 
systematically selected partial rows from the 27 possible ones, such that all 
combinations were exhausted. After generation of a particular matrix, columns 1, 
2, and 3 were checked for ordering. If ordering was present the matrix was 
"processed" to determine what logical function it produced; if not, a new matrix 
was generated. 

2.3 Processing of Matrices 

The processing of a given matrix was the key portion of the program 
since it was repeated so many times; hence it had to be made as economical as 
possible. The basic method of processing was the same as used by Hellerman, 
i.e., the output of the circuit was determined for each of the eight possible 
input combinations. The sequence of machine instructions used to accomplish 
this was different however, and is thought to be as efficient as possible, A 
given input combination was placed in the sense-indicator (Si) register. Then 
each bit position of the word for row 1 which was a one was compared with the 
corresponding bit in the SI register, using the ONT (on-test for indicators) 
instruction. If all corresponding positions were also one this meant that the 
output of the NAND element in row 1 was zero, and the computer skipped the next 
instruction. If any position was zero, this meant that the output of the NAND 
element was a one, and the machine executed the next instruction, which placed 
(via the OSI instruction) an additional one in the "column-7" position of the SI 
reigster. This process was then repeated for the remaining rows. 



3. COMMENTS ON THE RESULTS 

Not all of the 256 functions of three variables were generated by the 
circuits containing up to four NAND elements. Circuits for the ten remaining 
functions were found and are included in the table of results. They all contain 
five NAND elements and hence are minimal with respect to the number of elements, 
but they may not be minimal with respect to the number of inputs. 

The set of minimal NOR circuits is also given in Table 1. These 
were obtained directly from the minimal NAND circuits using the fact that any 
minimal NAND circuit realizing a function F(a,b,c) will also represent a minimal 
NOR circuit for the function G(a,b,c) where 

F(a,b,c) = G(a,b,c) 



-6- 



h, TABLE OK RESULTS 

Table 1 lists the minimal NOR and NAND realizations for the 
256 functions of three variables, assuming complemented inputs are available. 
The functions are listed according to an octal number which indicates which 
minterms are present in the canonical expansion of the function, Writing a 
given octal designation number as an 8-bit binary number (filling in left zeros 
if necessary), the bits, from left to right, indicate the presence or absence of 
the terms abc, abc, abc, abc, abc, abc, abc, abc. 

The circuit numbers and the corresponding inputs refer to the circuit 
diagrams following the table. A circuit number of zero indicates that the 
function requires no NAND element--it is either just a single literal or iden- 
tically zero or one. 

Several functions have two minimal realizations. In such cases the 
alternative realization is listed immediately following the main entry. 



-7- 



TABLE 1. 



Fen. 




NAND 








Inputs 


NOR 








Inputs 


No. 


Expression 


Cct. 


l 


2 


3 


k 


5 


6789 


Cct. 


1 


2 


3 


k 


5 6 7 8 9 






































1 


abc 


3 


a 


b 


c 








2 


a 


b 


c 






2 


abc 


3 


a 


b 


c 








2 


a 


b 


c 






3 


ab 


k 


a 


b 










1 


a 


b 








k 


abc 


3 


a 


b 


c 








2 


a 


b 


c 






5 


ac 


k 


a 


c 










1 


a 


c 








6 


a(bc+bc) 


7 


a 


b 


c 


a 


b 


c 


10 


b 


c 


b 


c 


a 


7 


a(b+c) 


6 


b 


c 


a 








5 


b 


c 


a 






10 


abc 


3 


a 


b 


c 








2 


a 


b 


c 






11 


a(bc+bc) 


7 


a 


b 


c 


a 


b 


c 


10 


c 


b 


b 


c 


a 


12 


ac 


k 


a 


c 










1 


a 


c 








13 


a(b+c) 


6 


b 


c 


a 








5 


c 


b 


a 






Ik 


ab 


k 


a 


b 










1 


a 


b 








15 


a(b+c) 


6 


c 


b 


a 








5 


b 


c 


a 






16 


a(b+c) 


6 


b 


c 


a 








5 


b 


c 


a 






IT 


a 





a 















a 










20 


abc 


3 


a 


b 


c 








2 


a 


b 


c 






21 


be 


k 


b 


c 










1 


b 


c 








22 


b(ac+ac) 


7 


b 


c 


a 


b 


c 


a 


10 


a 


c 


a 


c 


b 


23 


b(a+c) 


6 


c 


a 


b 








5 


a 


c 


b 






24 


c ( ab+ab ) 


7 


c 


a 


b 


c 


a 


b 


10 


a 


b 


a 


b 


c 


25 


c ( a+b ) 


6 


a 


b 


c 








5 


a 


b 


c 






26 


abc+abc+abc 


11 


a 


b 


c 


a 


b 


c a b c 


18 


a 


b 


a 


c 


b c a b c 


27 


ab+ac+bc 


12 


b 


c 


a 


b 


c 




12 


b 


c 


a 


b 


c 


30 


abc+abc 


7 


a 


b 


c 


a 


b 


c 


15 
16 


b 
b 


c 

a 


a 
c 


b 
a 


c a 
b c 


31 


abc+bc 


8 


b 


c 


a 


b 


c 




Ik 

12 


b 
a 


c 

c 


a 
b 


b 
b 


c 
c 


32 


ac+abc 


8 


a 


c 


a 


b 


c 


< 


Ik 
12 


a 

b 


c 

c 


b 

a 


a 
a 


c 
c 


33 


ac+bc 


9 


b 


c 


a 


c 






9 


a 


c 


b 


c 





TABLE 1 (CONT'D). 



Fcn< 
No. 



Expression 



NAND Inputs N ffl 
Cct. 12 3 4 5 6 7 8 9 Cct, 



Inputs 
123456789 



34 



45 



kG 



ab+abc 



35 


ab+bc 


36 


a(b+c)+abc 


37 


a+bc 


l+O 


abc 


l+l 


b(ac+ac) 


1+2 


be 


43 


b(a+c) 


kk 


abc+abc 



abc+ac 



bc+abc 



hi 


bc+ac 


50 


abc+abc 


51 


abc+abc+abc 


52 


c ( a+b ) 


53 


c(a+b)+ab 


54 


ab+abc 


55 


a(b+c)+abc 


56 


ab+bc 


57 


a+bc 


60 


ab 


61 


b(a+c) 


62 


b(a+c) 


63 


b 


61+ 


ab+abc 



a b a b c 



9 


a 


b 


c 


b 






13 


b 


c 


a 


b 


c 


a 


5 


b 


c 


a 








3 


b 


c 


a 








7 


b 


c 


a 


b 


c 


a 


1+ 


b 


c 










6 


a 


c 


b 








7 


b 


c 


a 


b 


c 


a 



65 



ab+ac 



8 c a b c a 

8 b c a b c 

9 b c a c 

7 a b c a b c 

11 abcabcabc 
6 abc 

12 a b c a b 

8 a b a b c 

13 b c a b a c 

9 abbe 

5 b c a 
1+ a b 

6 a c b 
6 cab 
b 

8 a b a b c 

9 abac 



11+ 
12 

9 
13 

6 
2 

10 
1 
5 
15 
16 
ll+ 

12 
11+ 
12 

9 

10 
18 

5 

12 

11+ 

12 

13 

9 

6 

1 

5 

5 



ik 

12 

9 



a b 

c b 

b c 

b c 

b c 

c a 

c a 

c b 

c a 

c a 

c b 

c a 

b a 

b c 

a c 

b c 

a b 

a b 

a b 

b c 

a b 

b c 

b c 

a b 

c b 

a b 

a c 

a c 
b 

b a 

c a 

a b 



cab 

a a b 

b a 

a b c a 

a 

b 

cab 

b 

b c a b 

a b c a 

b c a 

c c a 

abc 

b b c 

a c 

abc 

a c b c a b c 

c 

abc 

a c b 

a a b 

abac 

b c 

a 

b 
b 

c b a 
b b a 
a c 



TABLE 1 (CONT'D). 



10 



Fen, 
No, 



Expression 



NAND Inputs NOR 
Cct. 12 3 4 5 6 7 8 9 Cct, 



Inputs 
123456789 



66 b(a+c)+abc 

67 b+ac 
70 ab+ab c 



71 


b(a+c)+abc 


72 


ab+ac 


73 


b+ac 


74 


ab+ab 


75 


ab+ab+ac 



13 


c a b c a b 


15 


cab 


8 


a b a b c 



13 


c 


a 


b 


cab 


6 


a 


c 


b 




1J+ 


b 


a 


b 


c a 


12 


a 


c 


b 


b a 


13 


a 


c 


b 


a b c 


9 


a 


b 


a 


c 


6 


a 


c 


b 




9 


a 


b 


a 


b 


8 


a 


b 


c 


a b 



76 



ab+ab+ac 



a b a b c 



77 


a+b 


100 


abc 


101 


c( ab+ab) 


102 


abc+abc 



103 



abc+ab 



104 


be 


105 


c ( a+b ) 


106 


bc+abc 


107 


bc+ab 


110 


abc+abc 


111 


abc+abc+abc 


112 


ac+abc 


113 


a(b+c)+abc 


114 


b ( a+c ) 


115 


b(a+c)+ac 


116 


ac+bc 



1 


a 


b 










4 


a 


b 










3 


a 


b 


c 








2 


a 


b 


c 








7 


c 


a 


b 


c 


a 


b 


10 


a 


b 


a 


b 


c 




7 


a 


b 


c 


a 


b 


c 


15 


a 


b 


c 


a 


b 


c 
















16 


a 


c 


b 


c 


a 


b 


8 


a 


b 


c 


a 


b 




14 

12 


a 
c 


b 

b 


c 

a 


a 
a 


b 
b 




4 


b 


c 










1 


b 


c 










6 


a 


b 


c 








5 


b 


a 


c 








8 


b 


c 


a 


b 


c 




14 
12 


c 
a 


b 
b 


a 
c 


c 
c 


b 
b 




9 


b 


c 


a 


b 






9 


b 


a 


b 


c 






7 


a 


b 


c 


8 


b 


c 


10 


a 


c 


a 


c 


b 




11 


a 


b 


c 


a 


b 


c a b c 


18 


a 


b 


a 


c 


b 


c a b c 


8 


a 


c 


a 


b 


c 




14 
12 


a 
c 


c 

b 


a 

a 


b 
a 


c 
c 




13 


c 


b 


a 


c 


a 


b 


, !3 


c 


b 


a 


c 


a 


b 


6 


c 


a 


b 








5 


c 


a 


b 








12 


c 


a 


b 


c 


a 




12 


a 


b 


c 


a 


b 




9 


a 


c 


b 


c 






9 


b 


c 


a 


c 







TABLE 1 (CONT'D). 






Fen. 




NAND 








Inputs 


NOR 








Inputs 


No. 


Expression 


Cct. 


1 


2 


3 


4 


5 


6 7 8 9 


Cct. 


1 


2 


3 


4 


5 6 7 8 9 


117 


a+bc 


5 


c 


b 


8 








6 


b 


c 


a 






120 


ac 


4 


a 


c 










1 


a 


c 








121 


c ( a+b ) 


6 


b 


a 


C 








5 


a 


b 


c 






122 


ac+abc 


8 


a 


c 


a 


b 


c 




14 
12 


c 

b 


a 
a 


b 
c 


c 
c 


a 

a 


123 


ac+ab 


9 


a 


c 


a 


b 






9 


a 


b 


a 


c 




124 


c ( a+b ) 


6 


a 


b 


c 








5 


a 


b 


c 






125 


c 





c 















c 










126 


c(a+b)+abc 


13 


a 


b 


c 


a 


b 


c 


13 


a 


b 


c 


a 


b c 


127 


c+ab 


5 


a 


b 


c 








6 


a 


b 


c 






130 


ac+abc 


8 


a 


c 


a 


b 


c 




14 
12 


c 
a 


a 
b 


c 
c 


b 
c 


a 
a 


131 


c(a+b)+abc 


13 


a 


b 


c 


a 


c 


b 


13 


a 


b 


c 


a 


c b 


132 


ac+ac 


9 


a 


c 


a 


c 






9 


a 


c 


a 


c 




133 


ac+ac+bc 


14 
12 


c 
c 


a 
b 


c 

a 


a 
c 


b 
a 




8 


a 


c 


a 


b 


c 


134 


ac+ab 


9 


a 


c 


a 


b 






9 


a 


b 


a 


c 




135 


c+ab 


5 


a 


b 


c 








6 


b 


a 


c 






136 


ac+ac+bc 


14 
12 


c 

b 


a 
c 


b 
a 


c 
c 


a 
a 




8 


a 


c 


a 


b 


c 


137 


a+c 


1 


a 


c 










4 


a 


c 








140 


abc+abc 


7 


a 


b 


c 


a 


b 


c 


10 


b 


c 


b 


c 


a 


i4i 


abc+abc+abc 


11 


a 


b 


c 


a 


b 


c a b c 


18 


a 


c 


b 


c 


a b a b c 


ite 


bc+abc 


8 


b 


c 


a 


b 


c 




14 
12 


b 
c 


c 

a 


b 
b 


a 
b 


c 
c 


U3 


b(a+c)+abc 


13 


c 


a 


b 


c 


b 


a 


13 


c 


a 


b 


c 


b a 


144 


bc+abc 


8 


b 


c 


a 


b 


c 




14 
12 


c 
b 


b 

a 


c 
c 


a 
c 


b 
b 


145 


c(a+b)+abc 


13 


b 


a 


c 


b 


c 


a 


13 


b 


a 


c 


b 


c a 


146 


bc+bc 


9 


b 


c 


b 


c 






9 


b 


c 


b 


c 




147 


bc+bc+ab 


14 
12 


b 

b 


c 

a 


b 
c 


c 

b 


a 
c 




8 


b 


c 


a 


b 


c 

UNIVERSITY Of 



TABLE 1 (CONT'D) . 






Fen, 




NAND 








Inputs 






NOR 








Inputs 




No. 


Expression 


Oct. 


1 


2 


3 


k 


5 


6 


7 


8 9 


Cct. 


1 


2 


3 


k 


5 


6 7 


89 


150 


abc+abc+abc 


11 


a 


b 


c 


a 


5 


c 


a 


b c 


18 


a 


b 


a 


c 


b 


c a 


b c 


151 


c ( ab+ab ) +c ( ab+ab ) 


17 


a 


b 


c 


b 


c 


a 






17 


a 


b 


c 


b 


c 


a 




152 


c(a+b)+abc 


13 


a 


b 


c 


c 


a 


b 






13 


a 


b 


c 


c 


a 


b 




153 


ac+ab+bc+abc 


18 


a 


c 


a 


b 


b 


c 


a 


b c 


11 


a 


b 


c 


a 


b 


c a 


b c 


15^ 


b(a+c)+abc 


13 


c 


a 


b 


b 


c 


a 






13 


c 


a 


b 


b 


c 


a 




155 


a(b+c)+bc+abc 


18 


b 


c 


a 


c 


a 


b 


a 


b c 


11 


a 


b 


c 


a 


b 


c a 


b c 


156 


a(b+c)+bc+bc 


11+ 
12 


b 
c 


c 

a 


b 

b 


c 

b 


a 
c 








8 


b 


c 


a 


b 


c 






157 


a+bc+bc 


10 


b 


c 


b 


c 


a 








7 


b 


c 


a 


b 


c 


a 




160 


a(b+c) 


6 


b 


c 


a 












5 


b 


c 


a 










161 


a(b+c)+bc 


12 


b 


c 


a 


b 


c 








12 


c 


a 


b 


c 


a 






162 


bc+ca 


9 


b 


c 


c 


a 










9 


a 


c 


b 


c 








163 


b+ac 


5 


c 


a 


b 












6 


a 


c 


b 










164 


bc+ab 


9 


c 


b 


b 


a 










9 


a 


b 


b 


c 








165 


c+ab 


5 


b 


a 


c 












6 


a 


b 


c 










166 


bc+bc+ab 


Ik 
12 


b 
a 


c 

b 


a 
c 


b 
b 


c 
c 








8 


b 


c 


a 


b 


c 






167 


b+c 


1 


b 


c 














k 


b 


c 












170 


a(b+c)+abc 


13 


b 


c 


a 


a 


b 


c 






13 


b 


c 


a 


a 


b 


c 




171 


a(b+c)+abc+bc 


18 


a 


b 


a 


c 


b 


c 


a 


b c 


11 


a 


b 


c 


a 


b 


c a 


b c 


172 


b(a+c)+ac+ac 


Ik 

12 


c 

a 


a 
b 


c 
c 


a 
c 


b 
a 








8 


c 


a 


c 


a 


b 






173 


b+ac+ac 


10 


c 


a 


c 


a 


b 








7 


c 


a 


b 


c 


a 


b 




17^ 


c ( a+b ) +ab+ab 


Ik 

12 


a 

b 


b 
c 


a 
a 


b 

a 


c 

b 








8 


a 


b 


a 


b 


c 






175 


c+ab+ab 


10 


a 


b 


a 


b 


c 








7 


a 


b 


c 


8. 


b 


c 




176 


ab+bc+ac 


15 
16 


a 
b 


b 
c 


c 

a 


a 
b 


b 
a 


c 
c 






7 


a 


b 


c 


a 


b 


c 




177 


a+b+c 


2 


a 


b 


c 










- 


3 


a 


b 


c 










200 


abc 


3 


a 


b 


c 












2 


a 


b 


c 










201 


abc+abc 


7 


a 


b 


c 


a 


b 


c 






15 
16 


a 

b 


b 
c 


c 
a 


a 

b 


b 
a 


c 
c 





TABLE 1 (CONT'D). 






Fen. 




NAND 








Inputs 




NOR 








Inputs 




No. 


Expression 


Cct. 


1 


2 


3 


1+ 


5 6 7 


8 9 


Cct, 


1 


2 


3 


1+ 


5 


6 7 


8 9 


202 


c ( ab+ab ) 


7 


a 


b 


c 


a 


b c 




10 


a 


: 


a 


b 


c 






203 


abc+ab 


8 


a 


b 


a 


b 


c 




11+ 
12 


a 
b 


b 

c 


a 
a 


b 

a 


c 
b 






201+ 


b(ac+ac) 


7 


c 


a 


b 


c 


a b 




10 


c 


a 


c 


a 


b 






205 


abc+ac 


8 


c 


a 


c 


a 


b 




11+ 
12 


c 

a 


a 
b 


c 

c 


a 
c 


b 
a 






206 


abc+abc+abc 


11 


a 


b 


c 


a 


b c a 


b c 


18 


a 


b 


a 


c 


b 


c a 


b c 


207 


abc+a(b+c) 


13 


b 


c 


a 


a 


b c 




13 


b 


c 


a 


a 


b 


c 




210 


be 


1+ 


b 


c 










1 


b 


c 












211 


abc+bc 


8 


b 


c 


a 


b 


c 




11+ 
12 


b 
a 


c 
b 


a 
c 


b 

b 


c 
c 






212 


c ( a+b ) 


6 


a 


b 


c 








5 


b 


a 


c 










213 


ab+bc 


9 


a 


b 


b 


c 






9 


c 


b 


b 


a 








211+ 


b(a+c) 


6 


a 


c 


b 








5 


c 


a 


b 










215 


ac+bc 


9 


a 


c 


b 


c 






9 


b 


c 


c 


a 








216 


ab+ac+bc 


12 


c 


a 


b 


c 


a 




12 


b 


c 


a 


b 


c 






217 


a+bc 


5 


b 


c 


a 








6 


b 


c 


a 










220 


a(bc+bc) 


7 


b 


c 


a 


b 


c a 




10 


b 


c 


b 


c 


a 






221 


abc+bc 


8 


b 


c 


a 


b 


c 




11+ 
12 


b 
c 


c 

a 


b 
b 


c 

b 


a 
c 






222 


abc+abc+abc 


11 


a 


b 


c 


a 


b c a 


b c 


18 


b 


c 


a 


c 


a 


b a 


b c 


223 


abc+b(a+c) 


13 


c 


a 


b 


b 


c a 




13 


c 


a 


b 


b 


c 


a 




221+ 


abc+abc+abc 


11 


a 


b 


c 


a 


b c a 


b c 


18 


a 


c 


a 


b 


b 


c a 


b c 


225 


abc+c(a+b) 


13 


a 


b 


c 


c 


a b 




13 


a 


b 


c 


c 


a 


b 




226 


ab c +ab c +ab c +ab c 


17 


a 


b 


c 


b 


c a 




17 


a 


b 


c 


b 


c 


a 




227 


ab+ac+bc+abc 


18 


a 


b 


a 


c 


b c a 


b c 


11 


a 


b 


c 


a 


b 


c a 


b c 


230 


abc+bc 


8 


b 


c 


a 


b 


c 




11+ 
12 


b 
b 


c 

a 


b 
c 


c 

b 


a 
c 






231 


bc+bc 


9 


b 


c 


b 


c 




. 


9 


b 


c 


b 


c 








232 


c(a+b)+abc 


13 


b 


a 


c 


b 


c a 




13 


b 


a 


c 


b 


c 


a 




233 


bc+b(a+c) 


Ik 

12 


c 

b 


b 
a 


c 
c 


a 
c 


b 

b 




8 


b 


c 


a 


b 


c 







TABLE 1 (CONT'D). 






Fen. 
No. 


Expression 


NAND 
Cct. 


1 


2 


3 


Inputs 
456789 


NOR 
Cct. 


1 


2 


3 


Inputs 

4 5 6 7 8 9 


234 


b(a+c)+abc 


13 


c 


a 


b 


c 


b 


a 


13 


c 


a 


b 


c 


b a 


235 


bc+c(a+b) 


14 
12 


b 
c 


c 
a 


b 

b 


a 

b 


c 
c 




8 


b 


c 


a 


b 


c 


236 


c(a+b)+ab+abc 


18 


a 


c 


b 


c 


a 


babe 


11 


a 


b 


c 


a 


b c a b c 


237 


a+bc+bc 


10 


b 


c 


b 


c 


a 




7 


a 


b 


c 


a 


b c 


240 


ac 


4 


a 


c 










1 


a 


c 








241 


ac+abc 


8 


a 


c 


a 


b 


c 




14 
12 


c 

b 


a 
c 


b 
a 


c 
c 


a 
a 


242 


c ( a+b ) 


6 


b 


a 


c 








5 


a 


b 


c 






243 


ab+ac 


9 


a 


b 


a 


c 






9 


a 


c 


a 


b 




244 


ac+abc 


8 


a 


c 


a 


b 


c 




14 
12 


c 
c 


a 

b 


c 
a 


a 
c 


b 
a 


245 


ac+ac 


9 


a 


c 


a 


c 






9 


a 


c 


a 


c 




246 


c(b+a)+abc 


13 


a 


b 


c 


a 


c 


b 


13 


a 


b 


c 


a 


c b 


247 


ac+a(b+c) 


14 

12 


c 
a 


a 

b 


c 
c 


b 
c 


a 
a 




8 


a 


c 


a 


b 


c 


250 


c ( a+b ) 


6 


a 


b 


c 








5 


a 


b 


c 






251 


c(a+b)+abc 


13 


a 


b 


c 


a 


b 


c 


13 


a 


b 


c 


a 


b c 


252 


c 





c 















c 










253 


ab+c 


5 


a 


b 


c 








6 


a 


b 


c 






254 


ab+ac 


9 


a 


b 


a 


c 






9 


a 


c 


a 


b 




255 


ac+bc+ac 


14 
12 


c 

b 


a 

a 


b 
c 


c 

c 


a 
a 




8 


a 


c 


a 


b 


c 


256 


ab+c 


5 


a 


b 


c 








6 


b 


a 


c 






257 


a+c 


l 


a 


c 










4 


a 


c 








260 


a(b+c) 


6 


b 


c 


a 








5 


c 


b 


a 






261 


bc+ac 


9 


b 


c 


a 


c 






9 


a 


c 


b 


c 




262 


bc+ab+ac 


12 


a 


b 


c 


a 


b 




12 


c 


a 


b 


c 


a 


263 


b+ac 


5 


c 


a 


b 








6 


c 


a 


b 






264 


a(b+c)+abc 


13 


c 


b 


a 


c 


a 


b 


13 


c 


b 


a 


c 


a b 


265 


ac+c(a+b) 


14 
12 


a 
c 


c 

b 


a 
a 


b 

a 


c 
c 




8 


a 


c 


a 


b 


c 


266 


a(b+c)+bc+abc 


18 


a 


b 


a 


c 


b 


c a b c 


11 


a 


b 


c 


a 


b c a b c 



TABLE 1 (CONT'D). 






Fen. 




No. 


Expression 


267 


ac+ac+b 


270 


ab+bc 


271 


bc+ac+bc 


272 


ab+c 


273 


b+c 


27^ 


a(b+c)+ab 



NAND Inputs NOR 

Cct. 12 3^56789 Cct. 



Inputs 
123^56789 



275 a(b+c)+a(b+c) 



276 


ab+ab+c 


277 


a+b+c 


300 


ab 


301 


ab+abc 



302 



ab+abc 



303 


ab+ab 


30^ 


b(a+c) 


305 


ab+ac 


306 


b(a+c)+abc 


307 


ab+a(b+c) 


310 


b(a+c) 


311 


b(a+c)+abc 


312 


ab+ac 


313 


ab+ab +bc 


31k 


b 


315 


ac+b 


316 


ac+b 


317 


a+b 


320 


a(b+c) 



10 


a 


c 


a 


c 


b 




9 


b 


a 


b 


c 






Ik 


c 


b 


a 


c 


b 




12 


a 


b 


c 


c 


b 




5 


b 


a 


c 








1 


b 


c 










Ik 


a 


b 


c 


a 


b 




12 


c 


b 


a 


a 


b 




15 


a 


b 


c 


a 


b 


c 


16 


a 


c 


b 


c 


a 


b 


10 


a 


b 


a 


b 


c 




2 


a 


b 


c 








k 


a 


b 










8 


a 


b 


a 


b 


c 





a b c a b 



9 


a 


b 


a 


b 






6 


a 


c 


b 








9 


a 


b 


a 


c 






13 


a 


c 


b 


a 


b 


c 


ll+ 


b 


a 


b 


c 


a 




12 


a 


c 


b 


b 


a 




6 


a 


c 


b 








13 


c 


a 


b 


c 


a 


b 


9 


a 


b 


a 


c 






Ik 


b 


a 


c 


b 


a 




12 


c 


a 


b 


b 


a 







b 












5 


a 


c 


b 








5 


a 


c 


b 








1 


a 


b 










6 


c 


b 


a 









7 


a b 


cab 


c 


9 


b c 


a b 




8 


b c 


a b c 




6 


a b 


c 




k 


b c 






8 


a b 


cab 





a b c a b c 



7 


c 


a 


b 


c 


a 


b 


3 


a 


b 


c 








1 


a 


b 










Hi 


a 


b 


c 


a 


b 




12 


c 


a 


b 


a 


b 




Ik 


a 


b 


a 


b 


c 




12 


a 


c 


b 


a 


b 




9 


a 


b 


a 


b 






5 


a 


c 


b 








9 


a 


b 


a 


c 






13 


a 


c 


b 


a 


b 


c 


8 


a 


b 


a 


b 


c 




15 


c 


a 


b 








13 


c 


a 


b 


c 


a 


b 


9 


a 


b 


a 


c 






8 


a 


b 


a 


b 


c 







b 












6 


c 


a 


b 








6 


a 


c 


b 








k 


a 


b 










5 


b 


c 


a 









TABLE 1 (COM 1 '!)) 



16 



Fen. 




NAND 








Inputs 


NOR 








Inputs 


No, 


Expression 


Cct. 


1 


2 


3 


k 


5 


6789 


Cct, 


1 


2 


3 


k 


5 6 7 8 9 


321 


ab+bc 


9 


a 


b 


b 


c 






9 


a 


b 


b 


c 




322 


a(b+c)+abc 


13 


b 


c 


a 


b 


a 


c 


13 


b 


c 


a 


b 


a c 


323 


b ( a+c ) +ab 


Ik 

12 


a 
b 


b 
c 


a 
a 


c 

a 


b 
b 




8 


a 


b 


a 


b 


c 


32+ 


ac+bc+ab 


12 


b 


c 


a 


b 


c 




12 


a 


b 


c 


a 


b 


325 


c+ab 


5 


a 


b 


c 








6 


a 


b 


c 






326 


a(b+c)+bc+abc 


18 


a 


b 


a 


c 


b 


c a b c 


11 


a 


b 


c 


a 


b c a b c 


327 


ab+ab+c 


10 


a 


b 


a 


b 


c 




7 


a 


b 


c 


a 


b c 


330 


ac+bc 


9 


b 


c 


a 


c 






9 


b 


c 


a 


c 




331 


ab+bc+bc 


Ik 

12 


b 
a 


c 
c 


a 
b 


b 

b 


c 
c 




8 


b 


c 


a 


b 


c 


332 


c ( a+b ) +ac 


ik 

12 


c 

b 


a 
a 


b 
c 


c 

c 


a 
a 




8 


c 


a 


b 


c 


a 


333 


c ( a+b ) +c ( a+b ) 


15 
16 


c 
c 


a 
b 


b 
a 


c 

b 


a 
c 


b 
a 


7 


b 


c 


a 


b 


c a 


33^ 


ac+b 


5 


c 


a 


b 








6 


a 


c 


b 






335 


b+c 


1 


c 


b 










k 


b 


c 








336 


ac+ac+b 


10 


c 


a 


c 


a 


b 




7 


b 


c 


a 


b 


c a 


337 


a+b+c 


2 


c 


a 


b 








3 


b 


c 


a 






3+0 


a(b+c) 


6 


b 


c 


a 








5 


b 


c 


a 






3kL 


a(b+c)+abc 


13 


b 


c 


a 


b 


c 


a 


13 


b 


c 


a 


b 


c a 


342 


ab+bc 


9 


b 


c 


b 


a 






9 


a 


b 


c 


b 




3^3 


ab+ab+ac 


Ik 

12 


a 
c 


b 
b 


c 

a 


a 

a 


b 
b 




8 


a 


b 


a 


b 


c 


3kk 


ac+bc 


9 


a 


c 


b 


c 






9 


b 


c 


a 


c 




3^5 


ac+ab+ac 


Ik 

12 


a 
b 


c 

c 


b 
a 


a 

a 


c 
c 




8 


a 


c 


a 


b 


c 


3+6 


b(a+c)+bc 


1+ 
12 


b 
a 


c 
c 


a 
b 


b 
b 


c 
c 




8 


b 


c 


a 


b 


c 


3^7 


b(a+c)+b(a+c) 


15 
16 


b 
b 


c 

a 


a 
c 


b 
a 


c 

b 


a 
c 


7 


a 


b 


c 


a 


b c 


350 


ab+ac+bc 


12 


b 


c 


a 


b 


c 




12 


b 


c 


a 


b 


c 



TABLE L (CONT'D) 






Fen, 




NAND 








Inputs 


NOR 








Inputs 


No. 


Expression 


Cct. 


1 


2 


3 


k 


5 


6 7 8 9 


Cct. 


1 


2 


3 


1+56789 


351 


ab+ac+bc+abc 


18 


a 


b 


a 


c 


b 


c a b c 


11 


a 


b 


c 


a b c a b c 


352 


ab+c 


5 


a 


b 


c 








6 


a 


b 


c 




353 


ab+ab+c 


10 


a 


b 


a 


b 


c 




7 


c 


a 


b 


cab 


35^ 


ac+b 


5 


a 


c 


b 








6 


c 


a 


b 




355 


ac+ac+b 


10 


a 


c 


a 


c 


b 




7 


b 


c 


a 


b c a 


356 


b+c 


1 


b 


c 










k 


b 


c 






357 


a+b+c 


2 


a 


b 


c 








3 


a 


b 


c 




360 


a 





a 















a 








361 


a+bc 


5 


b 


c 


a 








6 


b 


c 


a 




362 


a+bc 


5 


b 


c 


a 








6 


c 


b 


a 




363 


a+b 


1 


a 


b 










k 


a 


b 






364 


a+bc 


5 


c 


b 


a 








6 


b 


c 


a 




365 


a+c 


1 


a 


c 










k 


a 


c 






366 


a+bc+bc 


10 


c 


b 


b 


c 


a 




7 


a 


b 


c 


a b c 


367 


a+b+c 


2 


a 


b 


c 








3 


a 


b 


c 




370 


a+bc 


5 


b 


c 


a 








6 


b 


c 


a 




371 


a+bc+bc 


10 


b 


c 


b 


c 


a 




7 


a 


b 


c 


a b c 


372 


a+c 


1 


a 


c 










k 


a 


c 






373 


a+b+c 


2 


a 


b 


c 








3 


a 


b 


c 




37^ 


a+b 


1 


a 


b 










h 


a 


b 






375 


a+b+c 


2 


a 


b 


c 








3 


a 


b 


c 




376 


a+b+c 


2 


a 


b 


c 








3 


a 


b 


c 




377 


1 





1 















1 









5. CIRCUIT DIAGRAMS 



Circuit 1 



Circuit 2 



Circuit 3 



L 






2 


^L 


3 




i>- 


^ 1 




5 1 




Circuit 


8 




Circuit 9 



Circuit k 



3- 



Circuit 5 



3- 
Circuit 6 



1 
2 

3 

5 
6 

7 
8 
9 



Circuit 10 



Circuit 11 





Circuit 7 



3 
,5 



Circuit 12 



-18- 






3 - 

k r 

5 — 

6 - 



Circuit 13 



Circuit 16 




Circuit Ik 




Circuit 17 



Circuit 15 




Circuit 1< 



6. CONCLUSION.: 

The results show that nearly all of the 256 functions of three 
variables can be generated using four or fewer NOR or NAND elements, and that 
that fan-out in all circuits is one. As in Hellerman's catalog, roughly half 
of the NAND circuits are those which result when the minimum-OR polynomial is 
rewritten in terms of the NAND connective. The analogous statement holds for 
NOR circuits. It is speculated that this fraction will get smaller and smaller 
as the number of variables in the function is increased. Nevertheless, the cir- 
cuit obtained from the minimum-OR polynomial serves as a good starting point in 
the search for a simple realization. One way in which the table could be used 
when more variables are present would be to decompose the function and use the 
circuits in the table to realize the constituents. 

This catalog, along with the one by Hellerman, should prove useful in 
the design of simple circuits. However, a more useful tool would be a computer 
program capable of producing, in a reasonable length of time, a minimal circuit 
for any arbitrary function. Perhaps such a program will be available in the 
future . 



-20- 



BIBLIOGRAPHY 



1. Earle, J., "Synthesizing Minimal Stroke and Dagger Functions," IRE Int. 
Conv. Record , Part 2, pp. 55-65; i960. 

2. Hellerman, L., "A Catalog of Three -Variable OR- Invert and AND- Invert Logical 
Circuits," IEEE Trans, on Electronic Computers , Vol. EC-12, pp. 198-223; 
June I963. 

3. Maley, G. A., and J. Earle, The Logic Design of Transistor Digital 
Computers , Prentice-Hall, Englewood Cliffs, N.J., Chap. 6; 1963. 

4. Scott, N. R., Analog and Digital Computer Technology , McGraw-Hill, New York, 
pp. ^31-^38; I960. 

5. Shubert, E. J., "Logical Design by Regression," Trans. AIEE , Vol, 80 
(Commun. and Electronics, No. 56), pp. 380- 383; September I96I. 



-21- 



a/ 



JVH 2 8 1969